Focusing on the certificate management problem in the traditional public key cryptography and the key escrow problem in identity-based cryptography, as well as the unfairness exposed on online transaction, a new Certificate-Based Verifiably Encrypted Signature (CBVES) scheme was proposed by combining the Verifiably Encrypted Signature (VES) with Certificate-Based Signature (CBS). Firstly, the security model of certificate-based verifiably encrypted signature scheme was defined; secondly, a new CBVES scheme was proposed based on the hardness of k-CAA (Collision Attack Algorithm with k traitors) problem and Squ-CDH (Square Computational Differ-Hellman) problem, and its safety was proved under the random oracle model. Compared with the previous CBVES, the proposed scheme is efficient, and has a small amount of calculation and only when the adjudicator and the verifier united, the ordinary signature can be recovered from the VES.